#!/usr/bin/env python
# -*- coding: UTF-8 -*-
'''
@Project ：PythonData 
@File    ：PTA_FInalExercise2.py
@Author  ：朱志文
@Date    ：2021/12/14 10:28 
'''

'''6-1 使用函数求特殊a串数列和 (10 分)
给定两个均不超过9的正整数a和n，要求编写函数fn(a,n) 求a+aa+aaa++⋯+aa⋯aa(n个a）之和，fn须返回的是数列和

函数接口定义：

fn(a,n)
其中 a 和 n 都是用户传入的参数。 a 的值在[1, 9]范围；n 是[1, 9]区间内的个位数。函数须返回级数和
裁判测试程序样例：

/* 请在这里填写答案 */

a,b=input().split()
s=fn(int(a),int(b))
print(s)'''

# def fn(a, n):
#     sum = 0
#     for i in range(1, n + 1):
#         sum += int(str(a) * i);
#     return sum
#
#
# a, b = input().split()
# s = fn(int(a), int(b))
# print(s)


'''6-2 使用函数求素数和 (10 分)
使用函数求素数和

prime(p), 其中函数prime当用户传入参数p为素数时返回True，否则返回False. PrimeSum(m,n),函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数1<=m<n。

函数接口定义：
在这里描述函数接口：
prime(p)，返回True表示p是素数，返回False表示p不是素数
PrimeSum(m,n)，函数返回素数和
裁判测试程序样例：

/* 请在这里填写答案 */

m,n=input().split()
m=int(m)
n=int(n)
print(PrimeSum(m,n))'''

# def primp(p):
#     for factor in range(2,int(p**0.5)+1):
#         if p%factor==0:
#             return False
#     return True if p!=1 else False;
# def PrimeSum(m,n):
#     sum=0;
#     for num in range(m,n+1):
#         if primp(num):
#             sum+=num
#     return sum
#
# m,n=input().split()
# m=int(m)
# n=int(n)
# print(PrimeSum(m,n))


'''
6-3 使用函数统计指定数字的个数 (10 分)
本题要求实现一个统计整数中指定数字的个数的简单函数。

CountDigit(number,digit )

其中number是整数，digit为[1, 9]区间内的整数。函数CountDigit应返回number中digit出现的次数。

函数接口定义：
在这里描述函数接口。例如：
CountDigit(number,digit ),返回digit出现的次数
裁判测试程序样例：

/* 请在这里填写答案 */

number,digit=input().split()
number=int(number)
digit=int(digit)
count=CountDigit(number,digit )
print("Number of digit 2 in "+str(number)+":",count)'''

# def CountDigit(number,digit ):
#     number=str(number)
#     return number.count(str(digit))


'''
6-4 使用函数输出指定范围内Fibonacci数的个数 (10 分)
本题要求实现一个计算Fibonacci数的简单函数，并利用其实现另一个函数,输出两正整数m和n（0<m<n≤100000）之间的所有Fibonacci数的数目。 所谓Fibonacci数列就是满足任一项数字是前两项的和（最开始两项均定义为1）的数列,fib(0)=fib(1)=1。其中函数fib(n)须返回第n项Fibonacci数；函数PrintFN(m,n)用列表返回[m, n]中的所有Fibonacci数。

函数接口定义：
在这里描述函数接口。例如：
fib(n),返回fib(n)的值
PrintFN(m,n)，用列表返回[m, n]中的所有Fibonacci数。
裁判测试程序样例：
在这里给出函数被调用进行测试的例子。例如：
/* 请在这里填写答案 */

m,n,i=input().split()
n=int(n)
m=int(m)
i=int(i)
b=fib(i)
print("fib({0}) = {1}".format(i,b))
fiblist=PrintFN(m,n)
print(len(fiblist))'''

# def fib(n):
#     a,b=1,1
#     for i in range(n):
#         a,b=b,a+b
#     return a
# def PrintFN(m,n):
#     fibs=[1,1]
#     for i in range(m,n):
#         fibs.append(fibs[-1]+fibs[-2])
#     fibItem=[]
#     for j in fibs:
#         if m<=j<=n:
#             fibItem.append(j)
#     return fibItem

'''
6-5 使用函数求余弦函数的近似值 (10 分)
本题要求实现一个函数，用下列公式求cos(x)近似值，精确到最后一项的绝对值小于eps（绝对值小于eps的项不要加）：


函数接口定义：funcos(eps,x ),其中用户传入的参数为eps和x；函数funcos应返回用给定公式计算出来，保留小数4位。

函数接口定义：
函数接口:
funcos(eps,x ),返回cos(x)的值。'''

# import math
# def funcos(eps,x ):
#     count=0
#     value=0
#     sym=0
#     while abs(x**count/math.factorial(count))>eps:
#         value=value+(x**count/math.factorial(count))*((-1)**sym)
#         sym+=1
#         count+=2
#     return value

'''
6-6 缩写词 (10 分)
缩写词是由一个短语中每个单词的第一个字母组成，均为大写。例如，CPU是短语“central processing unit”的缩写。

函数接口定义：
acronym(phrase);
phrase是短语参数，返回短语的缩写词'''

# def acronym(phrase):
#     inits=[]
#     for i in phrase.split():
#         inits.append(i[:1])
#     init=''
#     for j in inits:
#         init=init+''.join(j.upper())
#     return init

'''
6-7 求嵌套列表的平均值 (10 分)
Avg是一个求平均值的函数。它的参数是嵌套列表，求每个元素的平均值。每个元素是列表，至少有1个值。

函数接口定义：
在这里描述函数接口。例如：
 Avg(lst)
 lst是一个二维嵌套列表，该函数返回值是每个元素的平均值组成的列表。'''
# def Avg(lst):
#     avgList=[]
#     for listI in lst:
#         sum = 0
#         for j in listI:
#             sum+=j
#             avg=sum/len(listI)
#         avgList.append(avg)
#     return avgList

'''
6-8 求多项式的值 (10 分)
一元多项式可以用列表表示。如p(x)=1+3x+9x 4
 ,可以表示成列表[1,3,0,0,9]。输入列表表示的多项式和x的值，求多项式的值。

函数接口定义：
在这里描述函数接口。例如：
value(lst,x)
lst表示多项式，x代表具体的值。'''

# p(x)=lst[i]*(x**i)
# def polyvalue(lst,x):
#     sum=0
#     for i in range(len(lst)):
#         sum+=lst[i]*(x**i)
#     return sum

'''
7-1 大于身高的平均值 (10 分)
中小学生每个学期都要体检，要量身高，因为身高可以反映孩子的生长状况。现在，一个班的身高已经量好了，请输出其中超过平均身高的那些身高。程序的输入为一行数据，其中以空格分隔，每个数据都是一个正整数。程序要输出那些超过输入的正整数的平均数的输入值，每个数后面有一个空格，输出的顺序和输入的相同。

输入格式:
在一行输入中一个班的身高值，以空格分隔。

输出格式:
在一行输出超过输入的平均数的输入值，以空格分隔。'''

# def avgHigh(highs):
#     sum=0
#     for i in highs:
#         sum+=i;
#     avg=sum/len(highs)
#     superHighs=[]
#     for i in highs:
#         if i>avg:
#             superHighs.append(i)
#     return superHighs
# highs=list(map(int,input().split()))
# superHighs=avgHigh(highs)
# for i in superHighs:
#     print(i,end=' ')

'''
7-2 输出字母在字符串中位置索引 (10 分)
输入一个字符串，再输入两个字符，求这两个字符在字符串中的索引。

输入格式:
第一行输入字符串
第二行输入两个字符，用空格分开。

输出格式:
从右向左输出字符和索引，即下标最大的字符最先输出。每行一个。'''

# def locaIndex(str,a,b):
#     count=0
#     lstCount=[]
#     lst=[]
#     for i in str:
#         if i==a or i==b:
#             lst.append(i)
#             lstCount.append(count)
#         count+=1
#     return lst[::-1],lstCount[::-1]
#
# string=str(input())
# a,b=map(str,input().split())
# lst,lstCount=locaIndex(string,a, b)
# for i in range(len(lst)):
#     print(f'{lstCount[i]} {lst[i]}')

'''
7-3 求整数的位数及各位数字之和 (10 分)
对于给定的正整数N，求它的位数及其各位数字之和。(提示：把整数转换成字符串，列表，用sum和len函数)

输入格式:
输入在一行中给出一个正整数N。

输出格式:
在一行中输出N的位数及其各位数字之和，中间用一个空格隔开。'''


# def lenAndSum(N):
#     strN=str(N)
#     lenN=len(strN)
#     sum=0
#     for i in strN:
#         sum+=int(i)
#     return lenN,sum
# N=int(input())
# lenN,sum=lenAndSum(N)
# print(f'{lenN} {sum}')


'''
7-4 字符替换 (10 分)
本题要求编写程序，将输入字符串中的大写英文字母按以下对应规则替换，其他字符不变。(提示：转换表用元组实现）

原字母	对应字母
A	Z
B	Y
C	X
D	W
...	...
X	C
Y	B
Z	A
输入格式:
在一行中输入字符串

输出格式:
在一行中给出替换完成后的字符串。'''
#A:65 Z:90 ,B:66 Y:89

# def changeStr(str1):
#     lst=[]
#     for i in range(65,91):
#         lst.append(chr(i))
#     lst1=lst[::-1]
#     res=''
#     for j in str1:
#         if 'A'<=j<='Z':
#             index=lst.index(j)
#             res+=lst1[index]
#         else:
#             res+=''.join(j)
#     return res
# str1=str(input())
# print(changeStr(str1))


'''
7-5 删除字符 (10 分)
输入一个字符串 str，再输入要删除字符 c，大小写不区分，将字符串 str 中出现的所有字符 c 删除。提示：去掉两端的空格。

输入格式:
在第一行中输入一行字符 在第二行输入待删除的字符

输出格式:
在一行中输出删除后的字符串'''
# def delStr(string,chars):
#     string=string.strip()
#     chars=chars.strip()
#     str1=''
#     for i in string:
#         if i.upper()!=chars.upper():
#             str1+=''.join(i)
#     return str1
# str1=str(input())
# c=str(input())
# print(f'result: {delStr(str1,c)}')

'''
7-6 输出10个不重复的英文字母 (10 分)
随机输入一个字符串，把最左边的10个不重复的英文字母（不区分大小写）挑选出来。 如没有10个英文字母，显示信息“not found”

输入格式:
在一行中输入字符串

输出格式:
在一行中输出最左边的10个不重复的英文字母或显示信息“not found"'''

# def noRepeat(s):
#     count=0;
#     res=''
#     for i in s:
#         if 'A'<=i<='Z' or 'a'<=i<='z':
#             if i.upper() not in res.upper() and count<10:
#                 count+=1
#                 res+=''.join(i)
#     if count<10:
#         print('not found')
#     else:
#         print(res)
#
# s=str(input())
# noRepeat(s)


'''
7-7 逆序的三位数 (10 分)
程序每次读入一个正3位数，然后输出按位逆序的数字。注意：当输入的数字含有结尾的0时，输出不应带有前导的0。比如输入700，输出应该是7。

输入格式：
每个测试是一个3位的正整数。

输出格式：
输出按位逆序的数。'''

# def revNumber(num):
#     num=str(num)
#     num=num[::-1]
#     return int(num)
# num=int(input())
# print(revNumber(num))

'''
7-8 判断两个字符串是否为变位词 (10 分)
如果一个字符串是 另一个字符串的重新排列组合，那么这两个字符串互为变位词。比如，”heart”与”earth”互为变位 词，”Mary”与”arMy”也互为变位词。

输入格式:
第一行输入第一个字符串，第二行输入第二个字符串。

输出格式:
输出“yes”,表示是互换词，输出“no”,表示不是互换词。'''


# def isAnagram(str1, str2):
#     str1, str2 = list(str1), list(str2)
#     str1 = sorted(str1)
#     str2 = sorted(str2)
#     if str1 == str2:
#         print('yes')
#     else:
#         print('no')
#
#
# str1 = str(input())
# str2 = str(input())
# isAnagram(str1, str2)

'''
7-9 输入字符串，排序后输出最大字符及该字符在原字符串中的索引 (10 分)
输入字符串，排序后输出最大字符及该字符在原字符串中的索引。相同字符的索引取最大值。提示：用元组实现。

输入格式:
在一行输入字符串。

输出格式:
在一行输出字符和索引。'''

# def strIndex(s):
#     str=list(s)
#     str=sorted(str,reverse=True)
#     char=str[:1][0]
#     index=s[::-1].index(char)
#     return char,index
# s=str(input())
# char,index=strIndex(s)
# print(f'{char}   {len(s)-index-1}')


'''
7-10 计算有n个字符串中最长的字符串长度 (10 分)
编写程序，用于计算有n(1<n<10)个字符串中最长的字符串的长度。前导空格不要计算在内！

输入格式:
在第一行中输入n,接下的每行输入一个字符串

输出格式:
在一行中输出最长的字符串的长度'''

# def maxLen(lst):
#     maxlst=[]
#     for i in lst:
#         maxlst.append(len(i))
#     return max(maxlst)
# n=int(input())
# lst=[]
# for i in range(n):
#     s=str(input()).strip()
#     lst.append(s)
# print(f'length={maxLen(lst)}')

'''
7-11 位1的个数 (10 分)
输入一个非负整数，求它变成二进制后1的个数（提示：用bin函数）。

输入格式:
输入一个正整数。

输出格式:
输出1的个数。'''
# def lenOne(num):
#     num=bin(num)
#     num=num[2:]
#     count=0
#     for i in str(num):
#         if i=='1':
#             count+=1
#     return count
#
# n=int(input())
# print(lenOne(n))

'''
7-12 整数的二进制相加 (10 分)
输入两个整数，大小在[0,63]之间。求它们的二进制和，二进制用8位表示。

输入格式:
在一行输入一个整数，在另一行输入另一个整数。

输出格式:
输出它们的二进制和。'''

# def intPlus(num1,num2):
#     numPlus=num1+num2
#     num1=bin(num1)[2:]
#     num2=bin(num2)[2:]
#     numPlus=bin(numPlus)[2:]
#     print('{:08}'.format(int(num1)))
#     print('{:08}'.format(int(num2)))
#     print('--------')
#     print('{:08}'.format(int(numPlus)))
# num1=int(input())
# num2=int(input())
# intPlus(num1, num2)

'''
7-13 汉明距离 (10 分)
两个整数间的汉明距离指的是这两个数对应二进制位不同的位置的数目。输入两个整数x,y, 0<=x,y<=2 
31
 。输出x,y的汉明距离。

输入格式:
在一行输入x,y。

输出格式:
在一行输出x,y汉明距离。'''

# def distance(x,y):
#     count=0
#     x=bin(x)[2:]
#     y=bin(y)[2:]
#     x='{:032}'.format(int(x))
#     y='{:032}'.format(int(y))
#     for i in range(32):
#         if x[i]!=y[i]:
#             count+=1
#     return count
# x,y=map(int,input().split())
# print(distance(x, y))


'''
7-14 判断回文字符串 (10 分)
回文就是字符串中心对称，从左向右读和从右向左读的内容是一样的。 输入一个字符串，判断该字符串是否为回文，只考虑数字和字母字符，字母的大小写没有区别。

输入格式:
输入一个字符串。

输出格式:
是回文，一行输出yes,否则输出no。'''

# def isReply(s):
#     str1=''
#     for i in s:
#         if i.isalnum():
#             str1+=''.join(i)
#     str2=str1[::-1]
#     str1=list(str1)
#     str2=list(str2)
#     for i in range(len(str1)):
#         if str1[i].upper()==str2[i].upper():
#             res=True
#         else:
#             return False
#             break
#         return res
# s=str(input())
# if isReply(s):
#     print('yes')
# else:
#     print('no')


'''

7-15 输入一行字符串，并将它转换成10进制数输出 (10 分)
输入一行字符串，去掉非16进制字符，并将它转换成10进制数输出。

输入格式:
输入一行字符串。

输出格式:
输出16进制字符串和转换后的10进制数。'''

# def printTen(s):
#     lst=[]
#     s=list(s)
#     for i in s:
#         if '0'<=i<='9' or 'a'<=i<='f' or 'A'<=i<='F':
#             lst.append(i)
#     tenSix=''.join(lst)
#     return tenSix,int(tenSix,16)
#
#
# s=str(input())
# tenSix,ten=printTen(s)
# print(tenSix)
# print(ten)

'''
7-16 统计满足特定条件的字符数 (10 分)
输入字符串A(没有重复字符），输入字符串B，求在字符串A中字符的个数，这些字符必须同时又在字符串B中。提示：用in运算符。

输入格式:
一行输入字符串A。 一行输入字符串B。

输出格式:
一行输出字符数。'''
# def charCount(A,B):
#     count=0
#     for i in B:
#         if i in A:
#             count+=1
#     return count
# A=str(input())
# B=str(input())
# print(charCount(A, B))

'''
7-17 查验身份证 (10 分)
一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：

首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；然后将计算的和对11取模得到值Z；最后按照以下关系对应Z值与校验码M的值：

Z：0 1 2 3 4 5 6 7 8 9 10
M：1 0 X 9 8 7 6 5 4 3 2
现在给定一些身份证号码，请你验证校验码的有效性，并输出有问题的号码。

输入格式：
输入第一行给出正整数N（≤100）是输入的身份证号码的个数。随后N行，每行给出1个18位身份证号码。

输出格式：
按照输入的顺序每行输出1个有问题的身份证号码。这里并不检验前17位是否合理，只检查前17位是否全为数字且最后1位校验码计算准确。如果所有号码都正常，则输出All passed。'''

# def checkID(lst):
#     weights=[7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2]
#     M=['1','0','X','9','8','7','6','5','4','3','2']
#     count=0
#     for i in lst:
#         sum = 0
#         if not i[:17].isdigit():
#             print(i)
#             count+=1
#         else:
#             for j in range(len(i)-1):
#                 sum=sum+weights[j]*int(i[j])
#             if not M[sum%11]==i[17:]:
#                 print(i)
#                 count+=1
#     if count==0:
#         print('All passed')
# N=int(input())
# lst=[]
# for i in range(N):
#     s=str(input())
#     lst.append(s)
# checkID(lst)


'''
7-18 输出星期名缩写 (10 分)
输入一个1到7的数字，输出对应的星期名的缩写。
1 Mon
2 Tue
3 Wed
4 Thu
5 Fri
6 Sat
7 Sun

输入格式:
输入1到7之间数字

输出格式:
输出对应的星期名的缩写'''
# def weekNameAbb(n):
#     weebDic={1:'Mon',2:'Tue',3:'Wed',4:'Thu',5:'Fri',6:'Sat',7:'Sun'}
#     return weebDic.get(n)
# n=int(input())
# print(weekNameAbb(n))

'''
7-19 图的字典表示 (10 分)
捕获.JPG

图的字典表示。输入多行字符串，每行表示一个顶点和该顶点相连的边及长度，输出顶点数，边数，边的总长度。比如上图0点表示：
{'O':{'A':2,'B':5,'C':4}}。用eval函数处理输入，eval函数具体用法见第六章内置函数。

输入格式:
第一行表示输入的行数 下面每行输入表示一个顶点和该顶点相连的边及长度的字符串

输出格式:
在一行中输出顶点数，边数，边的总长度'''

# def picDirt(lst):
#     sides=0
#     sum=0
#     for dicts in lst:
#         for key in dicts:
#             # print(f'{key}:{dicts[key]}')
#             for i in dicts[key]:
#                 sides+=1
#                 sum+=dicts[key][i]
#     return len(lst),sides,sum
# N=int(input())
# lst=[]
# for _ in range(N):
#     dic=eval(input())
#     lst.append(dic)
# ver,sides,sum=picDirt(lst)
# print(f'{ver} {sides} {sum}')

'''
7-20 四则运算（用字典实现） (10 分)
四则运算（用字典实现），比较c语言的switch语句。

输入格式:
在一行中输入一个数字 在一行中输入一个四帜运算符(+,-,*,/) 在一行中输入一个数字

输出格式:
在一行中输出运算结果（小数保留2位）'''
# def opera(num1,ope,num2):
#     dic={'+':num1+num2,'-':num1-num2,'*':num1*num2,'/':num1/num2 if num2!=0 else 'divided by zero'}
#     return dic.get(ope)
# num1=int(input())
# ope=str(input())
# num2=int(input())
# print('%.2f'%opera(num1,ope,num2) if num2!=0 else opera(num1,ope,num2))


'''
7-21 分析活动投票情况 (10 分)
利用集合分析活动投票情况。第一小队有五名队员，序号是1,2,3,4,5;第二小队也有五名队员，序号6,7,8,9,10。输入一个得票字符串，求第二小队没有得票的队员

输入格式:
在一行中输入得票的队员的序列号，用逗号隔开。

输出格式:
一行中输出第二小队没有得票的队员序号。'''

# lst=list(map(int,input().split(',')))
# nolst=[]
# if not 5 in lst:
#     nolst.append('5')
# if not 6 in lst:
#     nolst.append('6')
# if not 7 in lst:
#     nolst.append('7')
# if not 8 in lst:
#     nolst.append('8')
# if not 9 in lst:
#     nolst.append('9')
# if not 10 in lst:
#     nolst.append('10')
# print(' '.join(nolst))


'''
7-22 统计字符出现次数 (10 分)
本题要求编写程序，统计并输出某给定字符在给定字符串中出现的次数。

输入格式：
输入第一行给出一个以回车结束的字符串（少于80个字符）；第二行输入一个字符。

输出格式：
在一行中输出给定字符在给定字符串中出现的次数。'''

# def appearCount(string,char):
#     count=0
#     for i in string:
#         if i==char:
#             count+=1
#     print(count)
# string=str(input())
# char=str(input())
# appearCount(string,char)


'''
7-23 统计工龄 (10 分)
给定公司N名员工的工龄，要求按工龄增序输出每个工龄段有多少员工。

输入格式:
输入首先给出正整数N（≤10 
5
 ），即员工总人数；随后给出N个整数，即每个员工的工龄，范围在[0, 50]。

输出格式:
按工龄的递增顺序输出每个工龄的员工个数，格式为：“工龄:人数”。每项占一行。如果人数为0则不输出该项。
'''

# def countWorkYear(lst):
#     lst_sort=sorted(set(lst))
#     for i in lst_sort:
#         print(f'{i}:{lst.count(i)}')
# N=int(input())
# lst=list(map(int,input().split()))
# if len(lst)==N:
#     countWorkYear(lst)


'''7-24 列表去重 (10 分)
输入一个列表，去掉列表中重复的数字，按原来次序输出！

输入格式:
在一行中输入列表

输出格式:
在一行中输出不重复列表元素
'''
# def listDeWeight(lst):
#     str1=set(lst)
#     print(' '.join(map(str,sorted(str1,key=lst.index))))
# lst=eval(input())
# listDeWeight(lst)

'''
7-25 能被3,5和7整除的数的个数（用集合实现） (10 分)
求指定区间内能被3,5和7整除的数的个数

输入格式:
在一行中从键盘输入2个正整数a,b（1<=a<b<=10000000），用空格隔开。

输出格式:
在一行输出大于等于a且小于等于b的能被3,5和7整除的数的个数。'''
# def exactDiv(a,b):
#     count=0
#     for i in range(a,b+1):
#         if i%5==0 and i%3==0 and i%7==0:
#            count+=1;
#     print(count)
# a,b=map(int,input().split())
# exactDiv(a, b)


'''
7-26 求矩阵鞍点的个数 (10 分)
一个矩阵元素的“鞍点”是指该位置上的元素值在该行上最大、在该列上最小。

本题要求编写程序，求一个给定的n阶方阵的鞍点。

输入格式： 输入第一行给出一个正整数n（1≤n≤6）。随后n行，每行给出n个整数，其间以空格分隔。

输出格式： 鞍点的个数'''
# def main(lst):
#     count=0
#     #i是行 j是列
#     for i in range(len(lst)):
#         for j in range(len(lst)):
#             if lst[i][j]==max(lst[i]):
#                 for k in range(len(lst)):
#                     if lst[i][j]>=lst[k][j] and i!=k:
#                         break
#                 else:
#                     count+=1
#     return count
# n=int(input())
# lst1=[]
# lst2=[]
# for i in range(n):
#     lst1.extend(list(map(eval,input().split())))
#     lst2.append(lst1)
#     lst1=[]
# if __name__=='__main__':
#     print(main(lst2))




'''
7-27 两数之和 (10 分)
给定一组整数，还有一个目标数，在给定这组整数中找到两个数字，使其和为目标数，如找到，解是唯一的。找不到则显示 "no answer"。输出的下标按从小到大排序。用一重循环加字典实现。

输入格式:
在一行中给出这组数。 在下一行输入目标数

输出格式:
在一行中输出这两个数的下标，用一个空格分开。'''

# def sumTwoNum(lst,r):
#     for i in range(len(lst)):
#         for j in range(i,len(lst)):
#             if lst[i]+lst[j]==r:
#                 return f'{i} {j}'
#                 break
#     return 'no answer'
# lst=list(map(int,input().split(',')))
# r=int(input())
# print(sumTwoNum(lst,r))


'''
7-28 字典合并 (10 分)
输入用字符串表示两个字典，输出合并后的字典。字典的键用一个字母或数字表示。注意：1和‘1’是不同的关键字！

输入格式:
在第一行中输入第一个字典字符串；

在第二行中输入第二个字典字符串。

输出格式:
在一行中输出合并的字典，输出按字典序。

"1" 的 ASCII 码为 49，大于 1，排序时 1 在前，"1" 在后。其它的字符同理。'''


# def main(dic1,dic2):
#     for key in dic1:
#         if key not in dic2:
#             dic2[key]=dic1[key]
#         else:
#             dic2[key]+=dic1[key]
#     ans = str(dict(sorted(dic2.items(), key=lambda item: item[0] if type(item[0]) == int else ord(item[0]))))
#     ans = ans.replace(' ', '').replace("'", '"')
#     print(ans)
# dict1=eval(input())
# dict2=eval(input())
# if __name__ == '__main__':
#     main(dict1,dict2)



# print(sorted(['1','a',1]))

'''
7-29 显示数字出现次数 (10 分)
输入一个十进制正整数，转换成16进制数。再输入一个数(0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f）,统计这个数出现的次数。

输入格式:
一行输入十进制正整数。 另一行输入要统计的数。

输出格式:
要统计的数出现的次数。
'''
# def appearNum(num, s):
#     count = 0
#     num=hex(num)[2:]
#     for key in str(num):
#         if key==s:
#             count+=1
#     print(count)
# num=int(input())
# s=str(input())
# appearNum(num, s)

'''
7-30 猴子选大王 (10 分)
一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入格式：
输入在一行中给一个正整数N（≤1000）。

输出格式：
在一行中输出当选猴王的编号。'''
# def main(N):
#     monkeys=[True]*N
#     counter,index,numbers=N,0,0
#     while counter!=1:
#         if monkeys[index]:
#             numbers+=1
#             if numbers==3:
#                 monkeys[index]=False
#                 numbers=0
#                 counter-=1
#         index+=1
#         index=index%N
#     for monkey in range(len(monkeys)):
#         if monkeys[monkey]:
#             print(monkey+1)
# N=int(input())
# main(N)


'''
7-31 特定矩阵元素和 (10 分)
给定一个n×n的方阵，本题要求计算该矩阵主、副对角线上的所有元素之和。主对角线为从矩阵的左上角至右下角的连线,副对角线为从矩阵的右上角至左下角的连线。。

输入格式:
输入第一行给出正整数n（1<n≤10）；随后n行，每行给出n个数，其间以空格分隔。

输出格式:
在一行中给出该矩阵主、副对角线的所有元素之和,保留两位小数。'''


# def main(lst):
#     sum=0
#     if len(lst)%2==1:
#         sum-=lst[int(3//2)][int(3//2)]
#     for row in range(len(lst)):
#         sum+=lst[row][row];
#         sum+=lst[row][len(lst)-1-row]
#     return sum
# n=int(input())
# lst1,lst2=[],[]
# for i in range(n):
#     lst1.extend(list(map(eval,input().split())))
#     lst2.append(lst1)
#     lst1=[]
# if __name__ == '__main__':
#     print('%.2f'%main(lst2))




'''
7-32 矩阵行、列、对角线和的最大值 (10 分)
求一个3*3矩阵每行、每列及对角线和的最大值。

输入格式:
在一行输入9个整数。

输出格式:
在一行输出每行、每列及对角线和的最大值。'''

# def main(lst):
#     sum_list=[]
#     sum_row=0
#     sum_line=0
#     sum_dia=0
#     sum_dia2=0
#     #row代表行 line代表列
#     for row in range(len(lst)):
#         for line in range(len(lst)):
#             sum_row+=lst[row][line]
#             sum_line+=lst[line][row]
#             sum_dia+=lst[line][line]
#             sum_dia2+=lst[line][len(lst)-line-1]
#         sum_list.append(sum_row)
#         sum_list.append(sum_line)
#         sum_list.append(sum_dia)
#         sum_list.append(sum_dia2)
#         sum_row=0
#         sum_line=0
#         sum_dia=0
#         sum_dia2=0
#     return sum_list
#
#
# lst=list(map(int,input().split()))
# lst1,lst2,lst3=[],[],[]
# lst_main=[]
# for i in range(3):
#     lst1.append(lst[i])
# for i in range(3,6):
#     lst2.append(lst[i])
# for i in range(6,9):
#     lst3.append(lst[i])
# lst_main.append(lst1)
# lst_main.append(lst2)
# lst_main.append(lst3)
#
# if __name__ == '__main__':
#     lst_res=main(lst_main)
#     print(max(lst_res))






'''
7-33 判断三角矩阵 (10 分)
本题要求编写程序，判断一个给定的方阵是否是三角矩阵。三角矩阵包含上三角矩阵和下三角矩阵两种。

上三角矩阵指主对角线以下的元素都为0的矩阵；下三角矩阵指主对角线以上的元素都为0的矩阵；主对角线为从矩阵的左上角至右下角的连线。

输入矩阵是三种情况之一(上三角矩阵、下三角矩阵或都不是)。

输入格式:
输入第一行给出一个正整数T，为待测矩阵的个数。接下来给出T个矩阵的信息：每个矩阵信息的第一行给出一个不超过10的正整数n。随后n行，每行给出n个整数，其间以空格分隔。

输出格式:
每个矩阵的判断结果占一行。如果输入的矩阵是上三角矩阵，输出“upper triangular matrix”，如果输入的矩阵是下三角矩阵，输出“lower triangular matrix”，都不是输出“no”。'''






'''
7-34 打印九九口诀表 (10 分)
下面是一个完整的下三角九九口诀表：

1*1=1   
1*2=2   2*2=4   
1*3=3   2*3=6   3*3=9   
1*4=4   2*4=8   3*4=12  4*4=16  
1*5=5   2*5=10  3*5=15  4*5=20  5*5=25  
1*6=6   2*6=12  3*6=18  4*6=24  5*6=30  6*6=36  
1*7=7   2*7=14  3*7=21  4*7=28  5*7=35  6*7=42  7*7=49  
1*8=8   2*8=16  3*8=24  4*8=32  5*8=40  6*8=48  7*8=56  8*8=64  
1*9=9   2*9=18  3*9=27  4*9=36  5*9=45  6*9=54  7*9=63  8*9=72  9*9=81  
本题要求对任意给定的一位正整数N，输出从1*1到N*N的部分口诀表。

输入格式：
输入在一行中给出一个正整数N（1≤N≤9）。

输出格式：
输出下三角N*N部分口诀表，其中等号右边数字占4位、左对齐。
'''

# def mnemonicTable(num):
#     for key in range(1,num+1):
#         for key2 in range(1,key+1):
#             print('{}*{}={:<4d}'.format(key2,key,key*key2),end='')
#         print()
#
# N=int(input())
# if 1<=N<=9:
#     mnemonicTable(N)

'''
7-35 求矩阵的局部极大值 (10 分)
给定M行N列的整数矩阵A，如果A的非边界元素A[i][j]大于相邻的上下左右4个元素，那么就称元素A[i][j]是矩阵的局部极大值。本题要求给定矩阵的全部局部极大值及其所在的位置。

输入格式：
输入在第一行中给出矩阵A的行数M和列数N（3≤M,N≤20）；最后M行，每行给出A在该行的N个元素的值。数字间以空格分隔。

输出格式：
每行按照“元素值 行号 列号”的格式输出一个局部极大值，其中行、列编号从1开始。要求按照行号递增输出；若同行有超过1个局部极大值，则该行按列号递增输出。若没有局部极大值，则输出“None 总行数 总列数”。'''


# def main(lst):
#     count=0
#     for i in range(1,len(lst)-1):
#         for j in range(1,len(lst[0])-1):
#             if lst[i][j]>lst[i][j-1] and lst[i][j]>lst[i][j+1] and lst[i][j]>lst[i-1][j] and lst[i][j]>lst[i+1][j]:
#                 count+=1
#                 print(lst[i][j],i+1,j+1)
#     if count==0:
#         print('None',len(lst),len(lst[0]))
# M,N=map(int,input().split())
# if 3<=M and N<=20:
#     lst1,lst2=[],[]
#     for i in range(M):
#         lst1.extend(list(map(eval,input().split())))
#         lst2.append(lst1)
#         lst1=[]
#     if __name__ == '__main__':
#         main(lst2)


'''
7-36 矩阵转置 (10 分)
从键盘输入一个m(2<=m<=6)*n(2<=n<=6)阶的矩阵，编程输出它的转置矩阵。

输入格式:
在第一行输入矩阵的行数m和列数n的值，在第二行按照矩阵格式输入矩阵的数据，同行数据之间用空格隔开。

输出格式:
矩阵格式输出，同行数据之间用一个空格隔开。'''
def main(lst):
    lst1=[]
    lst2=[]
    for i in range(len(lst[0])):
        for j in range(len(lst)):
            lst1.append(lst[j][i])
        lst2.append(lst1)
        lst1 = []
    return lst2

m,n=map(int,input().split())
lst1,lst2=[],[]
for i in range(m):
    lst1.extend(list(map(eval,input().split())))
    lst2.append(lst1)
    lst1=[]
if __name__ == '__main__':
    lst=main(lst2)
    for i in lst:
        print(" ".join('%s' %id for id in i))
'''
7-37 显示直角数字图形 (10 分)
本题目要求输入行数，输出指定行数的图形。

输入格式:
输入行数n,1<=n<=10

输出格式:
输出图形。'''

# def appearNum(n):
#     for i in range(n):
#         for j in range(i+1):
#             print(chr(65+j),end='')
#         print()
# n=int(input())
# if 1<=n<=10:
#     appearNum(n)



'''
7-40 输入列表，求列表元素和(eval输入应用） (10 分)
在一行中输入列表，输出列表元素的和。

输入格式:
一行中输入列表。

输出格式:
在一行中输出列表元素的和。'''
# def sumList(lst):
#     sum=0
#     for i in lst:
#         sum+=i
#     print(sum)
# lst=eval(input())
# if __name__=='__main__':
#     sumList(lst)

'''
7-41 一帮一 (10 分)
“一帮一学习小组”是中小学中常见的学习组织方式，老师把学习成绩靠前的学生跟学习成绩靠后的学生排在一组。本题就请你编写程序帮助老师自动完成这个分配工作，即在得到全班学生的排名后，在当前尚未分组的学生中，将名次最靠前的学生与名次最靠后的异性学生分为一组。

输入格式：
输入第一行给出正偶数N（≤50），即全班学生的人数。此后N行，按照名次从高到低的顺序给出每个学生的性别（0代表女生，1代表男生）和姓名（不超过8个英文字母的非空字符串），其间以1个空格分隔。这里保证本班男女比例是1:1，并且没有并列名次。

输出格式：
每行输出一组两个学生的姓名，其间以1个空格分隔。名次高的学生在前，名次低的学生在后。小组的输出顺序按照前面学生的名次从高到低排列。'''


# n = int(input())
# list0 = []
# list1 = []
# temp = []
# for i in range(n):
#     string = input()
#     if string[0] == '0':
#         temp = string.split()
#         temp.append(i)
#         list0.append(temp)
#     else:
#         temp = string.split()
#         temp.append(i)
#         list1.append(temp)
# for i in range(n // 2):
#     for j in range(n // 2):
#         if list0[j][2] == i:
#             print(list0[j][1], list1[n // 2 - 1 - j][1])
#         if list1[j][2] == i:
#             print(list1[j][1], list0[n // 2 - 1 - j][1])


'''
7-42 验证“哥德巴赫猜想” (10 分)
数学领域著名的“哥德巴赫猜想”的大致意思是：任何一个大于2的偶数总能表示为两个素数之和。比如：24=5+19，其中5和19都是素数。本实验的任务是设计一个程序，验证20亿以内的偶数都可以分解成两个素数之和。

输入格式：
输入在一行中给出一个(2, 2 000 000 000]范围内的偶数N。

输出格式：
在一行中按照格式“N = p + q”输出N的素数分解，其中p ≤ q均为素数。又因为这样的分解不唯一（例如24还可以分解为7+17），要求必须输出所有解中p最小的解。'''
# def isPrime(num):
#     for i in range(2,int(num**0.5)+1):
#         if num%i==0:
#             return False
#     return True if num!=1 else False
# def primeSum(N):
#     for p in range(2,N//2+1):
#         q=N-p
#         if isPrime(p) and isPrime(q):
#             if p+q==N:
#                 return p,q
#                 break
#
# N=int(input())
# if 2<=N<=2000000000 and N%2==0:
#     p,q=primeSum(N)
#     print(f'{N} = {p} + {q}')


'''
7-43 列表或元组的数字元素求和 (10 分)
求列表中数字和,列表中嵌套层次不限2层

输入格式:
在一行中输入列表或元组

输出格式:
在一行中输出数字的和'''

# def numSum(lst):
#     sum=0
#     for i in lst:
#         if type(i)==list or type(i)==tuple:
#             sum+=numSum(i)
#         elif type(i)==int:
#             sum+=i
#     return sum
#
# lst=eval(input())
# print(numSum(lst))

'''
7-44 列表数字元素加权和(1) (10 分)
输入一个嵌套列表，嵌套层次不限，根据层次，求列表元素的加权和。第一层每个元素 的值为：元素值*1，第二层每个元素的值为：元素值*2，第三层每个元素的值为：元素值*3， ...,以此类推！

输入格式:
在一行中输入列表

输出格式:
在一行中输出加权和'''

# def eleWeightSum(lst,weight):
#     sum=0
#     for i in lst:
#         if type(i)==int:
#             sum+=i*weight
#         elif type(i)==list:
#             weight+=1
#             sum+=eleWeightSum(i,weight)
#             weight-=1
#
#     return sum
# lst=eval(input())
# print(eleWeightSum(lst,1))

'''
7-45 列表元素个数的加权和(1) (10 分)
输入一个嵌套列表，嵌套层次不限，根据层次，求列表元素的加权个数和。第一层每个元素算一个元素，第二层每个元素算2个元素，第三层每个元素算3个元素，第四层每个元素算4个元素,...,以此类推！

输入格式:
在一行中输入一个列表。

输出格式:
在一行中输出加权元素个数值。'''

# def eleWeightSum(lst,weights):
#     sum=0
#     for i in lst:
#         if type(i)==int:
#             sum+=1*weights
#         elif type(i)==list:
#             weights+=1
#             sum+=eleWeightSum(i,weights)
#             weights-=1
#     return sum
# lst=eval(input())
# print(eleWeightSum(lst,1))

'''
7-46 求指定层的元素个数 (10 分)
输入一个嵌套列表，再输入层数，求该层的数字元素个数。

输入格式:
第一行输入列表 第二行输入层数

输出格式:
在一行中输出元素个数'''

# def eleLayerNum(lst,x,count):
#     sum=0
#     for i in lst:
#         if isinstance(i,int) and x==n:
#             sum+=1
#         elif isinstance(i,list):
#             sum+=eleLayerNum(i,x+1,count)
#     return sum
#
#
# lst=eval(input())
# x=1
# n=int(input())
# print(eleLayerNum(lst,x,n))























